#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType *elem; //整形指针，申请的堆空间起始地址存入elem
    int TableLen;   //存储动态数组里边元素的个数
}SSTable;
//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
//打印顺序表
void ST_Print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
void InsertSort(ElemType *A,int len)
{
    int i,j,insertVal;
    for (i = 1; i < len; ++i) {  //外层控制要插入的数
        insertVal=A[i]; //保存要插入的数
        //内层控制比较，j要大于等于0，同时A[j]大于insertVal时，A[j]的位置要往后覆盖
        for (j = i-1; j >=0&&A[j]>insertVal; j--) {
            A[j+1]=A[j];
        }
        A[j+1]=insertVal; //把插入的元素放到对应相等的位置
    }
}
/**
 *   j    i
 * 1 3  34 45
 * @return
 */
int main() {
    SSTable ST;
    ST_Init(ST,10);
    ST_Print(ST);
    InsertSort(ST.elem,10);
    ST_Print(ST);
    return 0;
}

